/*
 * $Id$
 *
 * Copyright (C) IUT Montreuil-University Paris 8, 2009-2010
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
 */

package fr.univ_paris8.iut.linc.align;


import java.io.IOException;
import java.net.URI;

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Set;

import org.semanticweb.owl.align.AlignmentException;
import org.semanticweb.owl.align.Cell;

import fr.inrialpes.exmo.align.impl.BasicAlignment;
import fr.inrialpes.exmo.align.impl.edoal.ClassConstruction;
import fr.inrialpes.exmo.align.impl.edoal.ClassDomainRestriction;
import fr.inrialpes.exmo.align.impl.edoal.ClassExpression;
import fr.inrialpes.exmo.align.impl.edoal.ClassId;
import fr.inrialpes.exmo.align.impl.edoal.ClassOccurenceRestriction;
import fr.inrialpes.exmo.align.impl.edoal.EDOALAlignment;
import fr.inrialpes.exmo.align.impl.edoal.EDOALCell;
import fr.inrialpes.exmo.align.impl.edoal.EDOALRelation;
import fr.inrialpes.exmo.align.impl.edoal.Expression;
import fr.inrialpes.exmo.align.impl.edoal.PathExpression;
import fr.inrialpes.exmo.align.impl.edoal.PropertyDomainRestriction;
import fr.inrialpes.exmo.align.impl.edoal.PropertyId;
import fr.inrialpes.exmo.align.impl.edoal.Comparator;
import fr.inrialpes.exmo.align.impl.edoal.RelationId;


import fr.inrialpes.exmo.align.parser.SyntaxElement.Constructor;
import fr.inrialpes.exmo.ontosim.string.JWNLDistances;
import fr.inrialpes.exmo.ontosim.string.StringDistances;
import fr.inrialpes.exmo.ontowrap.Ontology;




public class DetectionComplexCorrespondences {

ComplexAlignment ca;
SimpleAlignment sa;	
static double conf;


/**
 * Détecter des correspondances complexes (entre deux formules)
 */
public int ComplexCorrespondencesFF (Graph gh1,Graph gh2, Ontology O1, Ontology O2) throws AlignmentException, IOException
{
	boolean Equivalent = false;
	boolean SubsumesO2 = false;
	boolean SubsumesO1 = false;
	//Tableau qui va contenir les deux formules à aligner si le 1er sous-graphe subsume le deuxième
	ArrayList <Object> res1= new ArrayList <Object>();
	//Tableau qui va contenir les deux formules à aligner si le 2eme sous-graphe subsume le 1er
	ArrayList <Object> res2= new ArrayList <Object>();
	EDOALCell ec = null;
	EDOALRelation r = null;
	int k=0;
	//Parcourir tous les couple de concepts
	for (int i = 0; i<gh1.ListConcept.size(); i++) 
		for (int j = 0; j<gh2.ListConcept.size(); j++) {
			
			if (IsStructures (gh1.ListConcept.get(i),gh2.ListConcept.get(j),gh1, gh2)){
				
				//Vérifier si le 1er sous-graphe subsume le 2eme, si c'est la cas res1 va contenir les formules à aligner
				res1=Subsumption (gh1.ListConcept.get(i), gh2.ListConcept.get(j),gh1,gh2);
				//Vérifier si le 2eme sous-graphe subsume le 1er, si c'est la cas res2 va contenir les formules à aligner
				res2=Subsumption(gh2.ListConcept.get(j),gh1.ListConcept.get(i),gh2,gh1);
				
				//Les deux sous-graphes sont équivalents
				if ((res1.size()>0) && (res2.size()>0))
					{ 
						Equivalent = true;
						k++;
					}
				
				//Le premier sous-graphe subsume le deuxième
				else if (res1.size()>0)
				{
					SubsumesO1 = true;
					k++;
				}
				
				//Le deuxième sous-graphe subsume le premier
				else if (res2.size()>0){
					SubsumesO2 = true;
					k++;
				}
			if ((Equivalent) || (SubsumesO2) || (SubsumesO1))
			{
				//Générer une relation d'équivalence entre les deux sous-graphes
				if (Equivalent){
					r = new EDOALRelation("=");
					ec = new EDOALCell (null,(ClassExpression) res1.get(0),(ClassExpression)res1.get(1),r,(Double) res1.get(2));
					Equivalent=false;
				}
				//Générer une relation de subsomption (le 1er sous-graphe est subsumé par le deuxième)
				else if (SubsumesO2){
					r = new EDOALRelation("<");
					ec = new EDOALCell (null,(ClassExpression)res2.get(1),(ClassExpression) res2.get(0),r,(Double) res2.get(2));
					SubsumesO2=false;
				}
				//Générer une relation de subsomption (le 2eme sous-graphe est subsumé par le premier)
				else if (SubsumesO1){
					r = new EDOALRelation(">");
					ec = new EDOALCell (null,(ClassExpression) res1.get(0),(ClassExpression)res1.get(1),r,(Double) res1.get(2));
					SubsumesO1=false;
				}
				
				ca.complexAlignment.addAlignCell(ec);
			}
			
	}
}
	
	   
return k;
}

/**
 * Vérifier si un sous-graphe subsume un deuxième
 */

private ArrayList <Object> Subsumption (Concept C1, Concept C2,Graph O1,Graph O2 ) throws AlignmentException{
	ArrayList <Edge> Ev1 = RelatedEntities (C1, O1);
	ArrayList <Edge> Ev2 = RelatedEntities (C2, O2);
	ArrayList <Edge> tab = new ArrayList <Edge>();
	ArrayList <Object> res= new ArrayList <Object>();
	boolean[] found = new boolean [Ev2.size()];
	ArrayList <String> conf= new ArrayList <String>();
	boolean trouve;
	boolean sub = true;
	int i = 0;	
	double simp, simc;
	
	//Initialement, toutes les entités voisines ne sont pas encore visitées
	for (int k=0; k<Ev2.size();k++)
		found[k]=false;
	
	
	double confiance=0;
	//Parcourir toutes les entités voisines du premier sous-graphe
	while ((i<Ev1.size())&&(sub)){
		
		trouve = false;
		simp = 0.0; simc=0.0;
		tab.clear();
		conf.clear();
		
		//Chercher l'entité la plus similaire du deuxième sous-graphe à l'entité en question
		for (int j = 0; j<Ev2.size();j++){
			if (!found[j]){
				
			//Si l'entité voisine est un concept
			if ((Ev1.get(i).getCompoundType()==null)&&(Ev2.get(j).getCompoundType()==null)){
				//Si les deux points d'entrées aux sous-graphes représentent les sources des arcs
				if ((Ev1.get(i).getSource().equals(C1))&&(Ev2.get(j).getSource().equals(C2)))
					simc = VerifyConcept (Ev1.get(i).getSimpleType(),Ev2.get(j).getSimpleType(),
						Ev1.get(i).getTarget(),Ev2.get(j).getTarget(), O1, O2);
				//Si les deux points d'entrées aux sous-graphes représentent les cibles des arcs	
				else if ((Ev1.get(i).getTarget().equals(C1))&&(Ev2.get(j).getTarget().equals(C2)))
					simc = VerifyConcept (Ev1.get(i).getSimpleType(),Ev2.get(j).getSimpleType(),
						Ev1.get(i).getSource(),Ev2.get(j).getSource(), O1, O2);
				
				//Si la similarité des concepts est superieur à un seuil donné
				trouve=(simc>=ca.thresholdSim);	
				if (trouve){
						tab.add(Ev2.get(j));
						conf.add( Double.toString(simc));
					
					}	
			}
		
		//Si l'entité voisine est une propriété
		else if (((Ev1.get(i).getCompoundType()!=null)&&(Ev2.get(j).getCompoundType()!=null))){
			//Si les deux points d'entrées aux sous-graphes représentent les sources des arcs
			if ((Ev1.get(i).getSource().equals(C1))&&(Ev2.get(j).getSource().equals(C2)))
				simp = VerifyProp (Ev1.get(i).getCompoundType(),Ev2.get(j).getCompoundType(),
						Ev1.get(i).getTarget(),Ev2.get(j).getTarget(),O1,O2);
			//Si les deux points d'entrées aux sous-graphes représentent les cibles des arcs
			else if ((Ev1.get(i).getTarget().equals(C1))&&(Ev2.get(j).getTarget().equals(C2)))
				simp =  VerifyProp (Ev1.get(i).getCompoundType(),Ev2.get(j).getCompoundType(),
						Ev1.get(i).getSource(),Ev2.get(j).getSource(),O1,O2);
			//Si le point d'entrée du 1er sous-graphe représente la source (domaine) et le point d'entrée du 2eme sous-graphe représente la cible (co-domaine)
			else if ((Ev1.get(i).getSource().equals(C1))&&(Ev2.get(j).getTarget().equals(C2)))
				simp =  VerifyProp (Ev1.get(i).getCompoundType(),Ev2.get(j).getCompoundType(),
						Ev1.get(i).getTarget(),Ev2.get(j).getSource(),O1,O2);
			//Si le point d'entrée du 1er sous-graphe représente la cible (co-domaine) et le point d'entrée du 2eme sous-graphe représente la source (domaine)	
			else if ((Ev1.get(i).getTarget().equals(C1))&&(Ev2.get(j).getSource().equals(C2)))
				simp = VerifyProp (Ev1.get(i).getCompoundType(),Ev2.get(j).getCompoundType(),
						Ev1.get(i).getSource(),Ev2.get(j).getTarget(),O1,O2);
			
			//Si la similarité des propriétés est superieure à un seuil donné
			trouve=(simp>=ca.thresholdSim);
			if (trouve){
				conf.add(Double.toString(simp));
				tab.add(Ev2.get(j));
		}
		}
	}
	}
		if (tab.size()==0)
			sub = false;
		else 
			{
			
				int max = Max (conf);
				found[Ev2.indexOf(tab.get(max))]=true;
				confiance=confiance+ Double.parseDouble(conf.get(max));	
				i++;
			}
		
	}	
	
	//Si le sous-graphe de C1 subsume le sous-graphe de C2
	if (sub){	
		 
		 confiance=((Ev1.size()<Ev2.size()) ? confiance/(Ev1.size()) : (confiance/Ev2.size()));
		 //Générer la formule qui correspond au 1er sous-graphe
		 ClassExpression Formula1 = generateFormula (Ev1 ,C1, O1); 
		//Générer la formule qui correspond au 2eme sous-graphe
		 ClassExpression Formula2 = generateFormula (Ev2 ,C2, O2); 
		 if ((Formula1!=null)&&(Formula2!=null)){
			 res.add(Formula1);
			 res.add(Formula2);
			 res.add(confiance);
			}
		 
		
	 }
 
  return res;
}

/**
 * Détecter des correspondances complexes (entre concept simple et formule)
 */
public int ComplexCorrespondencesCF (Graph O1,Graph O2, int direction) throws AlignmentException
{
	ArrayList <Edge> e;
	int compt=0;
	EDOALCell ec = null;
	
	//Parcourir tous les concepts du premier sous-graphe
	for (int i = 0; i<O1.ListConcept.size();  i++) {
		ArrayList <Edge> Ev1 = RelatedEntities (O1.ListConcept.get(i), O1);
			//Parcourir toutes les entités voisines du concept en question
			for (int j=0; j<Ev1.size();j++)
				//Si l'entité voisine représente un super-classe du concept en question 
				if ((Ev1.get(j).getSimpleType().equals("SubClass"))
						&&(Ev1.get(j).getSource().equals(O1.ListConcept.get(i)))){
						//Chercher tous les généralisants de ce super-classe
						ArrayList <Concept> Sup = SuperClasses (O1.ListConcept.get(i),
								O1.ListConcept.get(i),O1,2);
						//Parcourir donc tous les généralisants (super-classe direct et tous ces généralisants)
						//du concept en question (O1.ListConcept.get(i))
						for (int k =0;k<Sup.size();k++){
							//Checher une formule de la 2eme ontologie qui peut être alignée avec le concept O1.ListConcept.get(i) de la première ontologie 
							e = FindEquiv (O1.ListConcept.get(i),Sup.get(k),O2);
								//Pour toutes les formules trouvées, il s'agit de générer les correspondances correspondantes				
								for (int l=0; l<e.size();l++){
									ec=GenerateCorrespondance (O1.ListConcept.get(i),e.get(l), direction);
									ca.complexAlignment.addAlignCell(ec);
									compt++;
								}
								
						}
			}
	}
	return compt;
}

/**
 * Générer une correspondance entre un concept simple et une formule
 */
private EDOALCell GenerateCorrespondance(Concept concept, Edge edge, int direction) throws AlignmentException {
	
	Set<ClassExpression> expressions = new LinkedHashSet<ClassExpression>();
	PathExpression path;
	EDOALCell ec = null;
	
	expressions.add(new ClassId(edge.getSource().getUri()));
	
	Comparator comp = Comparator (edge);	
	ClassExpression cl1 = new ClassId(concept.getUri());	
	
	path = new PropertyDomainRestriction(new ClassOccurenceRestriction
			(new PropertyId(edge.getCompoundType().getUri()),comp, 
					edge.getCompoundType().getCardinality()));
			
	ClassExpression cl2 = new ClassId(edge.getTarget().getUri());						
	expressions.add(new ClassDomainRestriction (path, cl2));

    ClassExpression res = new ClassConstruction( Constructor.AND, expressions);
	
	if (direction == 1) {
    EDOALRelation r = new EDOALRelation("<");
	ec = new EDOALCell (null,cl1 ,res ,r, conf);
	}
	else
	{
		EDOALRelation r = new EDOALRelation(">");
		ec = new EDOALCell (null,res ,cl1 ,r, conf);
	}
	return ec;
}



/**
 * Checher une formule du graphe O2 qui peut être alignée avec un concept c1 ayant comme généralisant le concept c2 
 */
private ArrayList <Edge> FindEquiv (Concept c1, Concept c2, Graph O2) throws AlignmentException{
	Concept nc;
	JWNLDistances jDist = new JWNLDistances();
	jDist.Initialize( ca.wndict, "3.0" );
	ArrayList <Edge> res = new ArrayList<Edge>();
	double conf1, conf2;
	
	//A partir de l'alignement simple, il s'agit de chercher un conpet du graphe O2 qui est equivalent au généralisant c2
	for (Cell c :   ((BasicAlignment) sa.SimpAlignment).getArrayElements()) {
		conf1=c.getStrength();
		
		if (((c.getObject1AsURI(sa.SimpAlignment).equals(c2.getUri()))||
				(c.getObject2AsURI(sa.SimpAlignment).equals(c2.getUri())))
				&&(conf1>=ca.thresholdSim)){
			
			if (c.getObject1AsURI(sa.SimpAlignment).equals(c2.getUri()))
				nc = new Concept ("<" + c.getObject2AsURI(sa.SimpAlignment) +">");
			else 
				nc = new Concept ("<" + c.getObject1AsURI(sa.SimpAlignment) +">");
			
					ArrayList <Edge> Ev2 = RelatedEntities (nc, O2);
					//Parcourir toutes les entités voisines de nc (concept qui est équivalent à c2)
					for (int j=0; j<Ev2.size();j++){
						//Si l'entité en question est une propriété
						if (Ev2.get(j).getCompoundType()!=null){
							String ch1 = c1.getLabel().toLowerCase();
							//si nc représente la source (domaine)
							if (Ev2.get(j).getSource().equals(nc)){
								//Verifier si cette propriéte est similaire syntaxiquement à c1
								String ch2 = Ev2.get(j).getCompoundType().getLabel().toLowerCase();
								conf2=1-StringDistances.smoaDistance(ch1,ch2);
								if (conf2>=ca.thresholdSim)
									res.add(Ev2.get(j));						
									conf=(conf1+conf2)/2;
							}
							//si nc représente la cible (co-domaine)
							else {
								//if (!ExistEdgeS (Ev2,nc,ch1)){
								
								//Verifier si cette propriéte est similaire syntaxiquement à c1
									String ch2 = Ev2.get(j).getCompoundType().getLabel().toLowerCase();
									conf2=1-StringDistances.smoaDistance(ch1,ch2);
									if (conf2>=ca.thresholdSim){
										String name=Ev2.get(j).getCompoundType().getName();
										//le "-" ici est ajouté pour désigner une propriété inverse, il est utilisé juste pour l'affichage
										//Mais lors de la transformation d'une ontologie sous forme de graphe, on cherche réellement les 
										//propriétés inverse à partir de l'ontologie
										String new_name=name.replace(Ev2.get(j).getCompoundType().getLabel(),
												Ev2.get(j).getCompoundType().getLabel()+"-");
										Property p=new Property(Ev2.get(j).getCompoundType().getRestriction(),
												Ev2.get(j).getCompoundType().getCardinality(),new_name);
										Edge e = new Edge (Ev2.get(j).getTarget(),Ev2.get(j).getSource(),
												Ev2.get(j).getSimpleType(),p);
										res.add(e);	
										conf=(conf1+conf2)/2;
									}
								}
					}
				
		}
	}
	
	}
	
	return res;
	
}

/*
private boolean ExistEdgeS (ArrayList <Edge> e,Concept cs, String ch){
	boolean trouve = false;
	int i=0;
	
	while ((i<e.size())&&(!trouve))
	{
		if (e.get(i).getCompoundType()!=null)
			if (e.get(i).getSource().equals(cs)){
				if (1-StringDistances.smoaDistance(ch.toLowerCase(),e.get(i).getCompoundType().getLabel()
					.toLowerCase())>=ca.thresholdSim)
					trouve=true;
				}
		i++;
		
	}
		
	return trouve;
	
}

*/


/**
 * Déterminer la cadinalité utilisée par une Cell EDOAL
 */
private Comparator Comparator (Edge e){
	
	Comparator comp = null;
	
	
		if (e.getCompoundType().getRestriction().equals("MinCardinality"))
	
					comp = Comparator.GREATER;					
		
		else if (e.getCompoundType().getRestriction().equals("MaxCardinality"))

			comp = Comparator.LOWER;	

		else comp = Comparator.EQUAL;	
				
	return comp;
}


/**
 * Générer une formule qui correspond à un sous-graphe donné, ayant comme point d'entrée le concept c1
 */
private ClassExpression generateFormula (ArrayList <Edge> e1,  Concept c1, Graph g1) {
		
		
		Set<ClassExpression> expressions = new LinkedHashSet<ClassExpression>();
		ArrayList <Edge> Ev = RelatedProperties (c1, g1);
		Comparator comp;
		PathExpression path;
		String name;
		URI uri = null;
		
		expressions.add(new ClassId(c1.getUri()));
		
		//Parcourir toutes les propriétés voisines
		for (int i = 0; i<e1.size();i++){
			if (e1.get(i).getCompoundType()!=null){
				comp = Comparator (e1.get(i));
				
				if (e1.get(i).getSource().equals(c1))	
					uri = Ev.get(i).getCompoundType().getUri();
					
				else if (e1.get(i).getTarget().equals(c1)){
					name=e1.get(i).getCompoundType().getName();
					//le "-" ici est ajouté pour désigner une propriété inverse, il est utilisé juste pour l'affichage
					//Mais lors de la transformation d'une ontologie sous forme de graphe, on cherche réellement les 
					//propriétés inverse à partir de l'ontologie
					String new_name=name.replace(e1.get(i).getCompoundType().getLabel(),e1.get(i).getCompoundType().getLabel()+"-");
					Property p = new Property (Ev.get(i).getCompoundType().getRestriction(),
							Ev.get(i).getCompoundType().getCardinality(),new_name);
					uri = p.getUri();
					
				
				}
				
				/*if (comp==null)
					path = new RelationId(uri);
				else*/
					path = new PropertyDomainRestriction(new ClassOccurenceRestriction
						(new PropertyId( uri),comp, 
						Ev.get(i).getCompoundType().getCardinality()));
						
				ClassExpression cl = new ClassId(Ev.get(i).getTarget().getUri());						
				expressions.add(new ClassDomainRestriction (path, cl));
			}		
		}
		
		ClassExpression res = new ClassConstruction( Constructor.AND, expressions);
		return res;
	}
	
	

/**
 * Déterminer si deux sous-graphes peuvent être alignés (composés au moin d'une propriété et un concept)
 */
private boolean IsStructures (Concept C1, Concept C2,Graph O1,Graph O2 ){
		boolean verify1 = false;
		boolean verify2 = false;
		boolean trouvec = false;
		boolean trouvep = false;
		ArrayList <Edge> Ev1 = RelatedEntities (C1, O1);
		ArrayList <Edge> Ev2 = RelatedEntities (C2, O2);
		int i = 0;
		
		while ((i<Ev1.size())&&(!verify1)){
			
			if (Ev1.get(i).getCompoundType()!=null)
					trouvep = true;
			else if (Ev1.get(i).getSimpleType()!=null)
					trouvec=true;
			if ((trouvep)&&(trouvec))
				verify1=true;
			else i++;
			}		
			
		i=0;
		trouvec=false;
		trouvep=false;
			
		while ((i<Ev2.size())&&(!verify2)){
				if (Ev2.get(i).getCompoundType()!=null)
					trouvep = true;
				else if (Ev2.get(i).getSimpleType()!=null)
					trouvec=true;
				if ((trouvep)&&(trouvec))
					verify2=true;
				else i++;
			}
			
		
		return (verify1 && verify2);
		
	}
	
	
	
 /**
 * Déterminer la similarité de deux concept appartenant à deux sous-graphes donnés
 */
private double VerifyConcept (String t1, String t2, Concept c1, Concept c2, Graph O1, Graph O2) throws AlignmentException
	{
		boolean Verify = false;
		double sim =0.0;
		
		//Il s'agit de vérifier le type de relation entre les concepts et les points d'entrée aux sous-graphes,
		//si on trouve le même type (Subclass, SuperClass ou DisjointWith), on calcule alors la similarité 
		//entre les concepts en prenant en considération les similarités entre leurs généralisants
		
		if (t1.equals("SubClass")&&(t2.equals("SubClass"))){
			sim=(Sim (c1, c2)>=SimSuperClasses(c1,c2,O1,O2)) ? Sim (c1, c2) : SimSuperClasses(c1,c2,O1,O2);
			if ((sim>=ca.thresholdSim)){
					Verify = true;				
					}
		}
		
		else if ((t1.equals("SuperClass")&&(t2.equals("SuperClass")))){
			sim=(Sim (c1, c2)>=SimSuperClasses(c1,c2,O1,O2)) ? Sim (c1, c2) : SimSuperClasses(c1,c2,O1,O2);
			if ((sim>=ca.thresholdSim)){
					Verify = true;				
					}
		}
		
		else if ((t1.equals("DisjointWith")&&(t2.equals("DisjointWith")))){
			sim = Sim (c1,c2);
			if (sim>=ca.thresholdSim)
				Verify = true;	
		}
			
		if (Verify)
			return sim;
		else return 0.0;
		
			
	}
	
	
	/**
	 * Déterminer la similarité entre deux concepts en prenant en considération les différents niveaux de 
	 * subsomption
	 */
private double SimSuperClasses (Concept c1, Concept c2, Graph O1, Graph O2) throws AlignmentException{
		
		int i,j;
		double sim=0.0;
		ArrayList <Concept> SupO1 = SuperClasses(c1,c1, O1,2);
		ArrayList <Concept> SupO2 = SuperClasses(c2,c2, O2,2);
		SupO1.add(c1);
		SupO2.add(c2);
		
		i = 0;
		
		
		while ((i<SupO1.size())&&(sim==0)){
			j=0;
			
			while ((j<SupO2.size())&&(sim==0.0)){
				sim=Sim (SupO1.get(i), SupO2.get(j));
				if (sim<ca.thresholdSim)
					j++;
			}
			if (sim==0.0)
				i++;
		}
		
	return sim;
	}


	/**
	 * Fonction récursive qui permet de chercher tous les super classes d'un concept donné pour un niveau donné
	 */
	public ArrayList <Concept> SuperClasses (Concept sub,Concept cls, Graph gh, int niveaux){
		
		ArrayList <Concept> Sup = gh.getSuperClasses(cls, gh);
		ArrayList <Concept> AllSup = new ArrayList<Concept>();
		ArrayList <Concept> x = new ArrayList<Concept>();
		
		if ((Sup==null))
			return null;
		else {
			if (niveaux > 0){
			for (int i =0; i<Sup.size(); i++){
				if ((!AllSup.contains(Sup.get(i)))&&(!Sup.get(i).getName().equals(sub.getName()))){
					
					AllSup.add(Sup.get(i));
					niveaux=niveaux-1;
					x=SuperClasses (sub, Sup.get(i), gh, niveaux);
					for (int j = 0 ;j<x.size();j++)
						if (!AllSup.contains(x.get(j)))
								AllSup.add(x.get(j));
				}
				
			}}
			return AllSup; 
		}
		
	}

	
	/**
	 * Déterminer la similarité de deux propriétés appartenant à deux sous-graphes donné ayant comme domaine 
	 * ou co-domaine les concepts c1 et c2
	 */
	private double VerifyProp (Property p1, Property p2, Concept c1, Concept c2,Graph O1, Graph O2) throws AlignmentException{
		boolean Verify = false;
		double simp=0.0;
		double simc=0.0;
		double sim=0.0;
		
		simp=Sim (p1, p2);
		//Si c1 et c2 sont owl:Thing ou rdfs:Literal, dans ce cas il s'agit de prendre en compte uniquement la similarité entre les propriétés
		if (Sim(c1, c2)==-1)
			sim = simp;
		//Sinon il s'agit de donner un poids plus fort aux concepts
		else{
		simc=(Sim (c1, c2)>=SimSuperClasses(c1,c2,O1,O2)) ? Sim (c1, c2) : SimSuperClasses(c1,c2,O1,O2);	
		sim = 0.6*simc + 0.4*simp;
		}
	//Si la similarité est supérieur à un seuil donné	
	if (sim>=ca.thresholdSim){
		
		//Si la cardinalité de la première propriété est plus générale que la cardinalité de la 2eme propriété
			if ((p1.getRestriction().equals(p2.getRestriction())&&(p1.getCardinality()==p2.getCardinality()))
					|| ((p1.getRestriction().equals("MaxCardinality"))&&(p2.getRestriction().equals("MaxCardinality"))
							&&(p1.getCardinality()>p2.getCardinality()))
					||((p1.getRestriction().equals("MinCardinality"))&&(p2.getRestriction().equals("MinCardinality"))
							&&(p1.getCardinality()<p2.getCardinality()))
					|| ((p1.getRestriction().equals("MinCardinality"))&&(p2.getRestriction().equals("ExactCardinality"))
							&&(p1.getCardinality()<=p2.getCardinality()))
					|| ((p1.getRestriction().equals("MaxCardinality"))&&(p2.getRestriction().equals("ExactCardinality"))
						&&(p1.getCardinality()>=p2.getCardinality())))
					
								{
									Verify = true;
									
									
								}
					}
	if (Verify)
		return sim;
	else
	return 0.0;


			
	}

	
/**
* Déterminer la similarité entre deux entités en utilisant la fonction de similarité choisie par l'utilisateur
*/
private double Sim (Entity e1, Entity e2) throws AlignmentException{

	double Sim = 0.0;
	Similarity s = new Similarity();
	if (ca.MethodSim.equals("SimEqualDistance"))
		Sim = s.SimEqualDistance(e1,e2);
	else if (ca.MethodSim.equals("SimSubStringDistance"))
		Sim = s.SimSubStringDistance(e1,e2);
	else if (ca.MethodSim.equals("SimAlignment"))
		Sim = s.SimAlignment(e1,e2);
	else if (ca.MethodSim.equals("SimWordNet"))
		Sim = s.simWordNet(e1,e2);
	else if (ca.MethodSim.equals("SimTest"))
		Sim = s.SimTest(e1,e2);
	
	return Sim;
}



/**
 * Chercher les entités voisines d'un concept donnée
 */
private ArrayList <Edge> RelatedEntities (Concept cls, Graph gh){
	ArrayList <Edge> relEnt = new ArrayList<Edge>();
	
	for (int i = 0; i<gh.ListEdge.size();i++) {
		if (((gh.ListEdge.get(i).getSource().equals(cls))||(gh.ListEdge.get(i).getTarget().equals(cls))))
		{
			Edge e = new Edge (gh.ListEdge.get(i).getSource(),gh.ListEdge.get(i).getTarget(),
					gh.ListEdge.get(i).getSimpleType(),gh.ListEdge.get(i).getCompoundType());
			relEnt.add(e);
		}
			
	}
	
	return relEnt;
}

/**
 * Chercher les propriétés voisines d'un concept donné
 */
private ArrayList<Edge> RelatedProperties(Concept cls, Graph gh) {

	ArrayList <Edge> relProp = new ArrayList<Edge>();
	
	for (int i = 0; i<gh.ListEdge.size();i++) {
		if ((gh.ListEdge.get(i).getCompoundType()!=null))
		{
			Edge e = new Edge (gh.ListEdge.get(i).getSource(),gh.ListEdge.get(i).getTarget(),
					null,gh.ListEdge.get(i).getCompoundType());
			relProp.add(e);
		}
			
	}
	return relProp;
}




private int Max (ArrayList <String> conf){
	int m=0;
	for (int i =1;i<conf.size();i++)
		if (Double.parseDouble(conf.get(i))>Double.parseDouble(conf.get(m)))
			m=i;
	
	return m;
	
}



public void afficher (ArrayList <Edge> e){
	System.out.println("Les entités reliées : ");
	for (int i = 0; i<e.size();i++) {
		
		if (e.get(i).getSimpleType()!="")
		System.out.println ("Source" + e.get(i).getSource().getName() + e.get(i).getSimpleType()
				+ "Target" + e.get(i).getTarget().getName());
		else 
			System.out.println ("Source" + e.get(i).getSource().getName() + e.get(i).getCompoundType().toString()
					+ "Target" + e.get(i).getTarget().getName());
	}
}

}